package main

type ListNode struct {
	Val  int
	Next *ListNode
}

/**
https://leetcode-cn.com/problems/merge-k-sorted-lists/
23. 合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
*/

func mergeTowLists(a *ListNode, b *ListNode) *ListNode {

	if a == nil || b == nil {
		if a == nil {
			return b
		} else {
			return a
		}
	}

	head := &ListNode{Val: 0, Next: nil}
	tail := head

	aPtr := a
	bPtr := b

	for aPtr != nil && bPtr != nil {
		if aPtr.Val < bPtr.Val {
			tail.Next = aPtr
			aPtr = aPtr.Next
		} else {
			tail.Next = bPtr
			bPtr = bPtr.Next
		}
		tail = tail.Next
	}

	if aPtr != nil {
		tail.Next = aPtr
	} else {
		tail.Next = bPtr
	}

	return head.Next
}

func merge(lists []*ListNode, left int, right int) *ListNode {
	if left == right {
		return lists[left]
	}

	if left > right {
		return nil
	}

	mid := (left + right) >> 1

	return mergeTowLists(merge(lists, left, mid), merge(lists, mid+1, right))

}

func mergeKLists(lists []*ListNode) *ListNode {

	return merge(lists, 0, len(lists)-1)
}

func main() {

}
